package backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 复原ip地址
 */
public class RestoreIPAddress {

    public static void main(String[] args) {
        String str = "25525511135";
        List<String> result = new ArrayList<>();
        backtrack(str,0,new ArrayList<>(),result);
        System.out.println(result);
    }

    private static void backtrack(String str,int startIndex,List<String> path,List<String> result) {
        if (startIndex == str.length() && path.size() == 4) {
            String res = String.join(".", path);
            result.add(res);
            return;
        }

        for (int i = startIndex; i < str.length(); i++) {
            String subStr = str.substring(startIndex,i+1);
            if (Long.parseLong(subStr) < 256) {
                path.add(subStr);
                backtrack(str,i+1,path,result);
                path.remove(path.size()-1);
            }
        }
    }
}
